package com.markus.code.动态规划;

import java.util.Arrays;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/16 14:02
 * todo: 子数组的最大累加和
 */
public class Class03_MaxSum {
    /**
     * 一维数组的问题
     */
    public int maxSum(int []arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        //这道题只需要两个变量，cur,max
        // cur ：遍历数组的过程中，加上当前数字(cur之前不为负数，如果为负数，直接置为0，然后从当前数字开始)
        // max ：在遍历过程中记录cur的最大值,最后返回这个max
        int cur = 0;
        int max = Integer.MIN_VALUE;
        for (int i=0;i<arr.length;i++){
            cur = cur < 0 ? 0 : cur;
            cur += arr[i];
            max = Math.max(max,cur);
        }
        return max;
    }

    /**
     * 下面来到扩展题：如果题目要求是二维的呢，要求返回二维数组中子矩阵最大的累加和
     */
    public int maxSumMatrix(int [][]matrix){
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return -1;
        }
        int resMax = Integer.MIN_VALUE;
        int []oneArr = new int[matrix[0].length];
        for (int i=0;i<matrix.length;i++){
            Arrays.fill(oneArr,0);
            for (int j=i;j<matrix.length;j++){
                //用于计算一维的子数组的最大累加和
                oneArr = getOneArr(matrix,oneArr,j);
                int sum = maxSum(oneArr);
                resMax = Math.max(resMax,sum);
            }
        }
        return resMax;
    }
    private int[] getOneArr(int [][]matrix,int[] oneArr,int row){
        for (int j = 0;j<oneArr.length;j++){
            oneArr[j] += matrix[row][j];
        }
        return oneArr;
    }

    public static void main(String[] args) {
        int arr[] = {3,-1,7,9,-100,9};
//        int matrix[][] = {{-5,2,3},{9,-7,100},{4,4,-900}};
        int[][] matrix = {{1,2,-1,4} , {2,0,5,1} , {1,-5,-1,4} , {-3,0,2,7}} ;
        Class03_MaxSum demo = new Class03_MaxSum();
        System.out.println(demo.maxSum(arr));
        System.out.println(demo.maxSumMatrix(matrix));
    }
}
